//题目:
// 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
// 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
// 示例 1：
// 输入: s = "leetcode", wordDict = ["leet", "code"]
// 输出: true
// 解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

// 示例 2：
// 输入: s = "applepenapple", wordDict = ["apple", "pen"]
// 输出: true
// 解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。

// 示例 3：
// 输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
// 输出: false
#include<iostream>
#include<vector>

using namespace std;
//代码
class Solution 
{
public:
    bool dfs(const string& s,int pos,const vector<string>& wordDict,string cur)
    {
        if(pos==s.size())
        {
            if(cur=="")
                return true;
            else 
                return false;
        }

        cur+=s[pos];
        //判断当前字符串有无匹配项
        for(auto& str:wordDict)
        {
            if(str==cur)
            {
                if(dfs(s,pos+1,wordDict,"")==true) return true;
                break;
            }
        }
        //没匹配成功，走下一步
        return dfs(s,pos+1,wordDict,cur);
    }
    bool wordBreak(string s, vector<string>& wordDict) 
    {
        //法一：全排列————超时
        // return dfs(s,0,wordDict,"");

        //法二：动态规划
        //1.创建dp表————dp[i]表示以第i个位置为结尾的字符串，能否由wordDict中的单词拼接而成
        vector<bool> dp(s.size());
        //2.初始化————这一步本题不需要
        //3.填表————动态转移方程，可分两部分：0...k...i [0,k]、[k+1,i] if(dp[k]==true && s.find(k+1,i))dp[i]=true;
        for(int i=0;i<s.size();i++)
        {
            for(int j=i-1;j>=0;j--)
                if(dp[j]==true && Find(s,j+1,i-j,wordDict)) dp[i]=true;
                
            if(dp[i]==false && Find(s,0,i+1,wordDict)) dp[i]=true;
        }   
        //4.确定返回值
        return dp[s.size()-1];
    }
    bool Find(const string& str,int begin,int len,const vector<string>& wordDict)
    {
        string tmp=str.substr(begin,len);
        for(const auto& s:wordDict)
            if(s==tmp)
                return true;
        return false;
    }
};